package com.c2b.algorithm.leetcode.base;

import java.util.Arrays;

/**
 * <a href='https://leetcode.cn/problems/relative-sort-array/'>数组的相对排序(Relative Sort Array)</a>
 * <p>给你两个数组，arr1 和 arr2，arr2 中的元素各不相同，arr2 中的每个元素都出现在 arr1 中。</p>
 * <p>对 arr1 中的元素进行排序，使 arr1 中项的相对顺序和 arr2 中的相对顺序相同。未在 arr2 中出现过的元素需要按照升序放在 arr1 的末尾。</p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6]
 *      输出：[2,2,2,1,4,3,3,9,6,7,19]
 *
 * 示例  2:
 *      输入：arr1 = [28,6,22,8,44,17], arr2 = [22,28,8,6]
 *      输出：[22,28,8,6,17,44]
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 *     <ul>
 *         <li>1 <= arr1.length, arr2.length <= 1000</li>
 *         <li>0 <= arr1[i], arr2[i] <= 1000</li>
 *         <li>arr2 中的元素 arr2[i]  各不相同 </li>
 *         <li>arr2 中的每个元素 arr2[i] 都出现在 arr1 中 </li>
 *     </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/12/19 15:48
 */
public class LC1112RelativeSortArray_S {

    static class Solution {
        public int[] relativeSortArray(int[] arr1, int[] arr2) {
            int left = 0;
            for (int num : arr2) {
                for (int right = left; right < arr1.length; right++) {
                    if (arr1[right] == num) {
                        int temp = arr1[right];
                        arr1[right] = arr1[left];
                        arr1[left] = temp;
                        ++left;
                    }
                }
            }
            Arrays.sort(arr1, left, arr1.length);
            return arr1;
        }

        /**
         * 计数排序
         */
        public int[] relativeSortArray2(int[] arr1, int[] arr2) {
            int max = 0;
            // 找出 arr1 中的最大值
            for (int num : arr1) {
                max = Math.max(max, num);
            }
            // count：用于统计 arr1 中每个数字出现的次数
            int[] count = new int[max + 1];
            for (int num : arr1) {
                ++count[num];
            }
            // 首先按照 arr2 中的顺序进行排序
            int currIndex = 0;
            for (int order : arr2) {
                for (int i = 0; i < count[order]; i++) {
                    arr1[currIndex++] = order;
                }
                count[order] = 0;
            }
            // 再按照升序进行排序
            for (int i = 0; i < max + 1; i++) {
                for (int j = 0; j < count[i]; j++) {
                    arr1[currIndex++] = i;
                }
            }
            return arr1;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        Printer.printArrayInt(solution.relativeSortArray2(new int[]{2, 3, 1, 3, 2, 4, 6, 7, 9, 2, 19}, new int[]{2, 1, 4, 3, 9, 6}));
        Printer.printArrayInt(solution.relativeSortArray2(new int[]{28, 6, 22, 8, 44, 17}, new int[]{22, 28, 8, 6}));
    }
}
